package com.yww.algorithm.sort;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author yww
 * @description 桶排序完善版
 * @since 2024/2/25 11:00
 */
public class BucketSortGeneric {
    public static void sort(int[] arr) {
        if (arr.length == 1) return;
        int max = arr[0];
        int min = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (max < arr[i]) {
                max = arr[i];
            } else if (min > arr[i]) {
                min = arr[i];
            }
        }

        // 准备桶
        int range = Math.max((max - min) / (arr.length - 1), 1);
        ArrayList<Integer>[] buckets = new ArrayList[(max - min) / range + 1];
        for (int i = 0; i < buckets.length; i++) {
            buckets[i] = new ArrayList<>();
        }

        for (int num : arr) {
            buckets[(num - min) / range].add(num);
        }
        int k = 0;
        for (ArrayList<Integer> bucket : buckets) {
            Integer[] array = bucket.toArray(new Integer[]{});
            insertionSort(arr);
            for (Integer integer : array) {
                arr[k++] = integer;
            }
        }
    }

    private static void insertionSort(int[] arr) {
        for (int low = 1; low < arr.length; low++) {
            int i = low - 1;
            int inserted = arr[low];
            while (i >= 0 && arr[i] > inserted) {
                arr[i + 1] = arr[i];
                i--;
            }
            if (i != low - 1) {
                arr[i + 1] = inserted;
            }
        }
    }

    public static void main(String[] args) {
        int[] a = {0};
        System.out.println(Arrays.toString(a));
        sort(a);
        System.out.println(Arrays.toString(a));
    }
}
